'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-11-06 09:26:11
'''
#
# @lc app=leetcode.cn id=1356 lang=python3
#
# [1356] 根据数字二进制下 1 的数目排序
#

# @lc code=start
from typing import List
class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        def count(a):
            ans=0
            while a:
                ans += 1 if a%2 else 0
                a//=2
            return ans
        import collections
        store = collections.defaultdict(list)
        for a in arr:
            store[count(a)].append(a)
        store = [(k, sorted(v)) for k, v in store.items()]
        store.sort()
        ans = []
        for _, v in store:
            ans.extend(v)
        return ans
# @lc code=end

